class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            dp[i][i] = 1

        for l in range(1, n):
            for i in range(0, n-l):
                j = i + l
                if l == 1:
                    dp[i][j] = dp[i][i] + dp[j][j]
                else:
                    #以两个节点作为根节点
                    dp[i][j] = dp[i+1][j] + dp[i][j-1]
                    for k in range(i+1, j):
                        dp[i][j] += dp[i][k-1] * dp[k+1][j]
        return dp[0][n-1]
